package com.sjf.day02.tree;

/**
 * 数组和顺序二叉树的相互转换
 *
 * @author <huangtang>
 * @since 2022/1/6 11:19
 **/
public class ArrBinaryTreeDemo {

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7};

        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);

        System.out.println("前序遍历");
        arrBinaryTree.preOrder();
        System.out.println();
        System.out.println("中序遍历");
        arrBinaryTree.midOrder();
        System.out.println();
        System.out.println("后序遍历");
        arrBinaryTree.postOrder();
    }


}

class ArrBinaryTree{
    private int[] arr;//存储数据节点的数组

    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }

    public void preOrder(){
        this.preOrder(0);
    }
    /**
     * 顺序存储二叉树的前序遍历
     * @param index 数组的下标
     */
    public void preOrder(int index){
        //如果数组为空
        if(arr == null || arr.length == 0){
            System.out.println("数组为空，无法前序遍历");
        }
        System.out.print(arr[index]+"\t"); //输出当前元素
        //递归向左遍历
        if((index * 2 + 1) < arr.length){
            preOrder(2*index+1);
        }
        //递归向右遍历
        if((index * 2 + 2) < arr.length){
            preOrder(2*index+2);
        }
    }

    public void midOrder(){
        this.midOrder(0);
    }
    /**
     * 中序遍历
     * @param index 数组的下标
     */
    public void midOrder(int index){
        //如果数组为空
        if(arr == null || arr.length == 0){
            System.out.println("数组为空，无法中序遍历");
        }
        //递归向左遍历
        if((index * 2 + 1)<arr.length){
            midOrder(index * 2 + 1);
        }
        System.out.print(arr[index]+"\t");
        //递归向左遍历
        if((index * 2 + 2)<arr.length){
            midOrder(index * 2 + 2);
        }
    }

    public void postOrder(){
        this.postOrder(0);
    }

    /**
     * 后序遍历
     * @param index 数组的下标
     */
    public void postOrder(int index){
        //如果数组为空
        if(arr == null || arr.length == 0){
            System.out.println("数组为空，无法后序遍历");
        }
        //递归向左遍历
        if((index * 2 + 1)<arr.length){
            postOrder(index * 2 + 1);
        }
        //递归向左遍历
        if((index * 2 + 2)<arr.length){
            postOrder(index * 2 + 2);
        }
        System.out.print(arr[index]+"\t");
    }
}
